package binarytree

// import "container/ring"

type TreeNode struct {
	Val         int
	Left, Right *TreeNode
}
// 删除BST中node
// 删除逻辑需要明确
func deleteNode(root *TreeNode, key int) *TreeNode {
	// 终止条件
	// 空
	if root == nil {   // 没有遇到要删除的节点---已经访问过叶子节点了
		return root
	}

	// 删除逻辑
	// 1. 叶子节点待删除 
	// 2. 左空右不空
	// 3. 右空左不空   补位
	// 4. 左右皆不空【star】:  左孩子执行右子树最左面节点的左孩子  返回右
	// 前序遍历
	if root.Val == key {
		// 1.2.3
		if root.Left==nil {
			return root.Right
		}else if root.Right == nil {
			return root.Left
		}else{// 4. 左右都不空
			rleft := root.Right   //右最左
			for rleft.Left != nil {
				rleft = rleft.Left
			}
			rleft.Left = root.Left
			// 删除
			// tmp = root
			root = root.Right
			// 释放tmp
			// tmp = nil  // gc处理
			return root   // 新节点返回上一层 上一层需要接
		}
	}
	// 左右
	if root.Val > key {
		root.Left = deleteNode(root.Left, key)
	}
	if root.Val < key {
		root.Right = deleteNode(root.Right, key)
	}
	return root  // 最后返回
}